1. Field of the Invention
The invention relates in general to signal-processing apparatus and in particular to networks for determining the Mth-largest value of an input data set. The invention has special relevance in those environments, such as image processing, where it is advantageous to perform this value determination in real time.
2. Description of the Prior Art
Presented here is the concept of an ordinal-value filter. This type of filter determines which one of a set of R applied data values is the Mth-largest. When R is odd and M is made equal to ((R+1)/2), the Mth-largest becomes the "middle" value of the data set, having in general an equal number of other data values both larger than and smaller than itself. Such a middle value is designated the median. A median filter is one which determines or selects this median value from an input data set.
Although both the basic concept of the median filter and its use in the field of image processing are well known, many prior realizations have depended upon time-consuming software routines.
Prior-art network concepts capable of being mechanized as hardware-economical, ordinal-value filters which perform the required determinations at the incoming data rate are presented by D. E. Knuth in Volume 3 of his book The Art Of Computer Programming: Sorting and Searching (1973). See especially the odd-even transposition sorting networks given in Knuth's FIG. 58 on page 241.
It should be noted, however, that the inventions claimed in this specification are considered to be patentably different from Knuth's concepts, as well as from the network concepts and mechanizations presented in the incorporated applications.
A real-time ordinal-value-filtering capability is extremely useful, especially, for example, in those situations where the ordinal-value processing of dynamic images is of greatest value when it can be performed as the images are occurring.